package myself.a010BinaryTreeRecursion;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/28
 * Time 10:01
 * Mail 739153436@qq.com
 */
public class LowestAncestor {
    // 给定一棵二叉树的头节点head，和另外两个节点a和b。返回a和b的最低公共祖先
    // 套路实现
    public static Node lowestAncestor2(Node head, Node a, Node b) {
        return process(head, a, b).ans;
    }

    public static Info process(Node random, Node a, Node b) {
        if (random == null) {
            return new Info(false, false, null);
        }
        Info left = process(random.left, a, b);
        Info right = process(random.right, a, b);

        Node ans = left.ans != null ? left.ans : (right.ans != null ? right.ans : null);
        if (ans == null) {
            boolean findA = right.findA || left.findA || random == a;
            boolean findB = right.findB || left.findB || random == b;
            if (findA && findB) {
                ans = random;
            }
            return new Info(findA, findB, ans);
        }
        return new Info(true, true, ans);
    }

    public static class Info {
        public boolean findA;
        public boolean findB;
        public Node ans;

        public Info(boolean fA, boolean fB, Node an) {
            findA = fA;
            findB = fB;
            ans = an;
        }
    }

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

}
